package day_2022_9_to_12.Day;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2022/09/20 16:37
 **/
public class Day18_1_Num698_CanPartitionKSubsets {
    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for(int num : nums) sum += num;
            if(sum % k != 0) return false;
            nums = Arrays.stream(nums).boxed().sorted((a1, a2)-> a2 - a1).mapToInt(int1 -> int1).toArray();
            int[] data = new int[k];
            return dfs(nums, data, 0, sum / k, k);
        }
        private boolean dfs(int[] nums, int[] data, int index, int target, int k){
            if(index == nums.length) return true;
            for(int i = 0; i < k; ++i){
                if(i > 0 && index == 0) break;
                if(data[i] + nums[index] > target) continue;
                if (i > 0 && data[i] == data[i - 1]) continue;
                data[i] += nums[index];
                if(dfs(nums, data, index+1, target, k)) return true;
                data[i] -= nums[index];
            }
            return false;
        }
    }
}